import java.util.*;

public class Leetcode {
}

//leetcode:2331:计算布尔二叉树的值
class Solution1 {
    public boolean evaluateTree(TreeNode root) {
        if(root.left == null){
            return root.val == 0 ? false : true;
        }

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);

        return root.val == 2 ? left | right : left & right;
    }
}

//leetcode:LCR:049:求根节点到叶结点数字之和
class Solution2 {
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }

    public int dfs(TreeNode root,int presum){
        presum = presum*10 + root.val;
        if(root.left == null && root.right == null){
            return presum;
        }
        int ret = 0;
        if(root.left != null) ret += dfs(root.left,presum);
        if(root.right != null) ret += dfs(root.right,presum);
        return ret;
    }
}

//leetcode:814:二叉树剪枝
class Solution3 {
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) return null;

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.val == 0 && root.left == null && root.right == null){
            return null;
        }else{
            return root;
        }
    }
}

//leetcode:98:验证二叉搜素树
class Solution4 {
    long prev =Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        boolean left = isValidBST(root.left);
        if(!left) return false;

        boolean ret = false;
        if(root.val > prev) ret = true;
        if(!ret) return false;

        prev = root.val;

        boolean right = isValidBST(root.right);
        return left && ret && right;
    }
}

//leetcode:230:二叉搜素树中第k小的元素
class Solution5 {
    int count;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }

    public void dfs(TreeNode root){
        if(root == null || count == 0) return;

        dfs(root.left);
        count--;
        if(count == 0) ret = root.val;
        dfs(root.right);
    }
}

//leetcode:257:二叉树的所有路径
class Solution6 {
    List<String> ret;
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        dfs(root,new StringBuilder());
        return ret;
    }
    public void dfs(TreeNode root,StringBuilder _path){
        StringBuilder path = new StringBuilder(_path);
        path.append(Integer.toString(root.val));
        if(root.left == null && root.right == null){
            ret.add(path.toString());
            return;
        }
        path.append("->");
        if(root.left != null) dfs(root.left , path);
        if(root.right != null) dfs(root.right,path);
    }
}